
/*
回溯
连接：https://leetcode.cn/problems/letter-case-permutation/description/
题目：784. 字母大小写全排列


    3. 解法：
    算法思路：
    只需要对英⽂字⺟进⾏处理，处理每个元素时存在三种情况：
    1. 不进⾏处理；
    2. 若当前字⺟是英⽂字⺟并且是⼤写，将其修改为⼩写；
    3. 若当前字⺟是英⽂字⺟并且是⼩写，将其修改为⼤写。
    递归函数设计：void dfs(int step
    参数：step（当前需要处理的位置）；
    返回值：⽆；
    函数作⽤：查找所有可能的字符串集合，并将其记录在答案列表。
    从前往后按序进⾏递归，递归流程如下：
    1. 递归结束条件：当前需要处理的元素下标越界，表⽰处理完毕，记录当前状态并返回；
    2. 对当前元素不进⾏任何处理，直接递归下⼀位元素；
    3. 判断当前元素是否为⼩写字⺟，若是，将其修改为⼤写字⺟并递归下⼀个元素，递归结束时撤销修
    改操作；
    4. 判断当前元素是否为⼤写字⺟，若是，将其修改为⼩写字⺟并递归下⼀个元素，递归结束时撤销修
    改操作；
*/
class Solution {
public:
    vector<string> ret;
    vector<string> letterCasePermutation(string s) {
        dfs(s,"",0);
        return ret;
    }
    void dfs(string& s,string path,int pos)
    {
        if(path.size()==s.size())
        {
            ret.push_back(path);
            return ;
        }
        if(s[pos]>='a' && s[pos]<='z')
        {
            char ch = s[pos]-32;
            dfs(s,path+ch,pos+1);
        }
        else if(s[pos]>='A' && s[pos]<='Z')
        {
            char ch = s[pos]+32;
            dfs(s,path+ch,pos+1);
        }
        dfs(s,path+s[pos],pos+1);
    }
};